package com.xufx.algorithm.dynamicplan;

/**
 * CoinChange
 * leetcode 322
 */
public class CoinChange {
    public static void main(String[] args) {
        int[] coins = new int[]{2,5,7};
        int target  = 12;
        int result =  coinChange(coins, target);
        System.out.println(result);
    }

    private static int coinChange(int[] coins, int target){
        int[] f = new int[target + 1];
        f[0] = 0;
        int n = coins.length;
        for(int i = 1; i <= target; i++){
            f[i] = Integer.MAX_VALUE;
            for (int coin : coins){
                if(i >= coin && f[i - coin] < Integer.MAX_VALUE)
                f[i] = Math.min(f[i - coin] + 1, f[i]);
            }
        }
        if (f[target] == Integer.MAX_VALUE){
            f[target] = -1;
        }
        return f[target];
    }
}
